Fermat's Little Theorem

Fermat's Little Theorem is a special case of Euler's theorem which predates it.

It is also the basis for a primality test known as Fermat's test for primality.

Theorem

Given for any prime number \(p\) and integer \(a\) such that \(\mathrm{gcd}(a, p) = 1\):

\[ a^{p - 1} \equiv 1 \pmod p.\]

Proof

There are many ways to prove this above fact, however the following proof shows that it is a special case of a simple result in group theory.

Consider the multiplicative group of \(\mathbb{Z}_n\) \(\mathbb{U}_p\), which has order \(\varphi(p) = p - 1\). Since \(\mathrm{gcd}(a, p) = 1\), we know that \(a \in \mathbb{U}_p\) (potentially after reducing modulo \(p\)).

Now any any group, a group element to the power of the group's order is the identity. Given that the order of this group is \(p - 1\), we hence have that:

\[ a^{p - 1} \equiv 1 \pmod p.\]

Proof

The map \(x \mapsto ax\) is a bijection of \(\mathbb{Z}_p\) for any \(a\) satisfying \(p \not\mid a\). As such, as a permutation of the terms, we have the equality

\[ 1 \cdot 2 \cdot 3 \cdot \dots \cdot (p - 1) \equiv a \cdot 2a \cdot 3a \cdot \dots \cdot a(p - 1) \pmod p.\]

Therefore we can conclude that

\[ a^{p - 1}(p - 1)! = (p - 1)! \pmod p\]

and then because \(p\) is prime, \(p \not\mid (p - 1)!\) so this element has an inverse in \(\mathbb{Z}_p\) and

\[ a^{p - 1} = 1 \pmod p.\]

Corollary

Given a prime number \(p\), and any \(a \in \mathbb{Z}\):

\[ a^{p} \equiv a \pmod p.\]

If choosing to start with this result and prove it directly, it can be used to prove the first result, with division by \(a\) only possible if \(a\) is invertible, which introduces the coprimality condition.

Proof

This result can be simply proven by multiplying by \(a\) in the first result. The condition of co-primality is therefore dropped as any element which is not coprime to a prime \(p\) is a multiple of \(p\), and hence both sides of the congruence are \(0\).